package 算法.NiuKe.JZ;

/**
 * @author:谢君臣
 * @Date:2021/3/2214:10
 * @version:1.0
 * @function:
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
 * 请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 */
public class JZ25 {
    public static void main(String[] args) {
        RandomListNode root = new RandomListNode(7);
        root.next = new RandomListNode(13);
        root.next.random = root;
        root.next.next = new RandomListNode(11);
        root.next.next.next = new RandomListNode(10);
        root.next.next.next.next = new RandomListNode(1);
        root.next.next.random = root.next.next.next.next;
        root.next.next.next.random = root.next.next;
        root.next.next.next.next.random = root;
        RandomListNode clone = Clone(root);
        System.out.println();
    }
    public static RandomListNode Clone(RandomListNode pHead) {
        if (pHead==null)
            return null;
        RandomListNode res = new RandomListNode(pHead.label);
        RandomListNode p = pHead.next;
        RandomListNode q = res;
        while (p!=null){   // 复制链表
            q.next = new RandomListNode(p.label);
            p = p.next;
            q = q.next;
        }
        p = pHead;
        q = res;
        // 复制random 指针
        while (p!=null){
            if (p.random!=null){
                int index = getIndex(pHead,p);
                RandomListNode temp = res;
                while (index>0){ temp = temp.next;index--;}
                q.random = temp;
            }
            p = p.next;
            q = q.next;
        }

        return res;
    }
    public static int getIndex(RandomListNode root,RandomListNode p){
        int index = 0;
        while (root!=p.random){
            root = root.next;
            index++;
        }
        return index;
    }

}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
